The invention relates to the field of collision avoidance. More particularly, the present invention relates to the use of eigenvalues associated with intersecting degenerate quadric surfaces for preferred use in collision prediction, warning and avoidance methods.
As the US Satellite Catalog transitions from general perturbations to special perturbations, the positional accuracy of each object will be readily available in the form of a covariance matrix, as well as providing position data for specifying object position vectors relative to past, present and future time. These covariances and position data can be propagated forward in time to predict a probability of collision between objects, or a probability of radio frequency interference caused by objects traversing a transmission channel path, or the probability of over flying an object subject to incidental laser illumination by another laser beam source object. Because the probability calculations can be computationally burdensome, it is desirable to prescreen candidate objects based on user-defined thresholds. Specifically, the future state of each object can be represented by a covariance-based ellipsoid and then processed to determine when the objects share a point in space that is in common during spatial coincidence. Primary and second ellipsoids and respective projections that do not touch or overlap each other can be eliminated from further processing. To date, all ellipsoidal prescreening methods involve numerical searches. For computational efficiency, such prescreening often models object as virtual spheres or virtual keep-out boxes that have much larger volumes than the respective objects but allow for quick distance comparisons. One disadvantage of the keep-out screening method is that large volumes can sound many false warnings. The virtual keep-out boxes may be found to be in projected spatial coincidence, yet the respective object will flyby with safe separation flyby distances. Hence, the keep-out screening method unnecessarily processes many objects as collision candidates for further and unnecessary processing, when there is no prospective collision potential. When considering the thousands of space objects currently catalogued, these screening methods result in increased unnecessary downstream computational processing that increases operator workload to further analyze potential satellite conjunctions in order to take evasive action when deemed necessary. The screening method would, for example, unnecessarily close a launch window when there is an insignificantly low probability of collision.
The traditional screening approaches to intersection determination have been based on a constrained numerical optimization formulation in which a requisite combined rotational, translational, and dimensional transformation reduces the secondary ellipsoid to a sphere, and then numerically searches the surface of the primary ellipsoid to obtain the point on the primary ellipsoid closest to the center of the sphere. Intersection is then determined according to whether this shortest distance exceeds the radius of the sphere.
The screening methods use direct substitution and voluminous algebraic simplification that is disadvantageously laborious and cumbersome to derive formulation for rapid determination of spatial coincidence. The general problem of analytically determining the intersection of any pair of surfaces has been performed for simple objects such as lines, spheres, and planes, but has disadvantageously not been applied to determining spatial coincidence of ellipsoids.
The formulation of conics and quadrics has been described for modeling the surface of two-dimensional and three-dimensional objects respectively. For example, two dimensional degenerate conics have been used to compute the common points shared by two ellipses using an extradimensional matrix. However, this two dimensional degenerate conics formulation is so computationally complex that it is impracticable for real time determination of the projected collisions and is only applied for two dimensional objects. These and other disadvantages are solved or reduced using the invention.
An object of the invention is to provide a method for determining when two volumes share the same space.
Another object of the invention is to provide a method for computing eigenvalues associated with potentially intersecting surfaces, and comparing the eigenvalues for determining when the surfaces intersect.
Yet another object of the invention is to provide a method for computing eigenvalues associated with potentially intersecting surfaces for an extradimensional product matrix, and comparing the eigenvalues for determining when the surfaces intersect.
Yet a further object of the invention is to provide a method for computing eigenvalues of an extradimensional product matrix associated with intersecting quadric surfaces of objects for determining when the object share common volume.
Still another object of the invention is to provide a method for computing eigenvalues of an extradimensional product matrix associated with quadric surfaces for determining when projected areas of the surfaces share common area.
The invention is directed to an analytical method for determining when two surfaces have common spatial points for indicating intersection. For example, the analytical method can be used for determining when two ellipsoids share the same volume. The method involves adding an extra dimension to the solution space for providing an extradimensional product matrix and examining eigenvalues that are associated with degenerate quadric surfaces, and then comparing the eigenvalues. A subset of the computed eigenvalues that are associated with intersecting degenerate quadric surfaces are computed and compared. The method can also be used to determine when two ellipses appear to share the same projected area based on a viewing angle. The method applies to all quadric surfaces particularly including ellipsoids. The method expands two-dimensional degenerate conics by examining the associated eigenvalue behavior for predicting shared volumes, area and points. The mathematical formulation of the conditions for intersection of the two surfaces are described by quadric forms.
In the preferred form, the method takes the 3xc3x973 covariance matrix of a primary ellipsoid object, and places the 3xc3x973 covariance matrix in the top three rows and columns of a primary extended extradimensional 4xc3x974 matrix. The other seven elements are set to zero, except the last fourth-row fourth-column element, which is set to xe2x88x921. The covariance matrix of the secondary ellipsoid object is firstly inverted and then extended into a secondary extended extradimensional 4xc3x974 matrix. The remaining elements are set to represent the relative position between the primary and secondary object in quadric form. These two new extended extradimensional matrices are then multiplied, and the eigenvalues are computed, and the computed eigenvalues are examined to determine when the primary and secondary ellipsoids share the same volume. When the ellipsoids share the same volume in projected time in spatial coincidence, appropriate action can be taken to avoid collision. Of special interest is the application to the case of two positional error ellipsoids in the three dimensional space associated with the pairwise close encounters arising from thousands of space orbiting objects listed in the satellite catalog. These error ellipsoids are obtained from the covariance matrices associated with these tracked objects. The determination of intersection can be rapidly used in projected collision predictions in order to eliminate cases which that not require further detailed analysis.
The method is based on formulating the intersecting problem in four dimensions and then determining the eigenvalues of the associated degenerate quadric surface. By using abstract symbolism and invariant properties of the extended (n+1) by (n+1) matrix, the analysis is greatly simplified and the overall structure made comprehensive. The method relies on numerical observations of the eigenvalues to arrive at the conclusion whether these ellipsoids intersect. The method may also be extended in two ways. The first way, the method can be extended as valid for quadric surfaces in general including ellipsoids, elliptic paraboloids, hyperbolic paraboloids, hyperboloids of one or two surfaces, elliptic cylinders and double cones. The method can be extended to n dimensions in which the intersection determination of nth-dric surfaces is described by quadric forms in n dimensions. The method provides direct computed eigenvalue results without approximation, iteration, or any form of numerical search. The method is computationally efficient in that no dimensional distortions, coordinate rotations, transformations, or eigenvector computations are needed. The method provides direct share volume results based on comparisons of the eigenvalues that can be rapidly computed without dimensional distortions, coordinate rotations, transformations, or eigenvector computations.
The method is computationally efficient with no scaling, rotating, or transformations. The invention can be applied to satellite collision prediction and avoidance, radio frequency impingement analysis and mitigation, incidental laser illumination determination and shutter control, air traffic control, computer graphics, robotics, and cloud penetration modeling. For example, computer graphics users, such screening could be used to invoke a hidden line removal algorithm. In these applications, geometric objects need to be modeled for determining when object surfaces collide, intersect or obscure each other. These and other advantages will become more apparent from the following detailed description of the preferred embodiment.